#include <iostream>
#include "MaxHeap.hpp"
using namespace std;

// 创建空堆，指定MaxSize
MaxHeap Create(int MaxSize)
{
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
    H->Element = (int *)malloc((MaxSize + 1) * sizeof(int)); // MaxSize+1是因为从数组下标为1的地方存放
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Element[0] = MaxData; //定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作
    return H;
}
// 判断堆是否为空
bool IsEmpty(MaxHeap H)
{
    return (H->Size == 0);
}
// 判断堆是否已满
bool IsFull(MaxHeap H)
{
    return (H->Size == H->Capacity);
}
// 将item插入最大堆H中
void Insert(MaxHeap H, int item)
{
    int i;
    if (IsFull(H))
    {
        cout << "MaxHeap Is Full" << endl;
        return;
    }
    i = ++H->Size; // i指向插入后，堆中的最后一个元素的位置
    // 将插在堆末尾的item与其父节点进行比较，如果比父节点大，则将父节点的
    // 值放在子节点位置，继续向上过滤
    // 考虑到向上过滤到根结点依旧是最大元素的可能性，此次没有判断i>1
    // 是因为Element[0]存放的是哨兵，一定比item大
    for (; H->Element[i / 2] < item; i /= 2)
    {
        H->Element[i] = H->Element[i / 2];
    }
    H->Element[i] = item; //将item插入
}
// 从最大堆H中取出键值最大的元素，并删除一个节点，返回取出的最大值
int DeleteMax(MaxHeap H)
{
    int Parent, Child;
    int MaxItem, temp;
    if (IsEmpty(H))
    {
        cout << "最大堆为空" << endl;
        return;
    }
    MaxItem = H->Element[1]; //取出根节点，即为最大值
    // 剔除根结点后，将最后一个叶子节点，即Element[Size]放到根结点位置，
    // 然后向下过滤保证最大堆的有序性
    // 此处使用Size--，后置递减运算符，将自身递减后，将递减前的value带入运算
    // 因此temp传入的是原Element[Size]
    temp = H->Element[H->Size--];
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child)
    {
        Child = Parent * 2; //此刻Child为左儿子
        if ((Child != H->Size) && (H->Element[Child] < H->Element[Child + 1]))
            Child++; //此条语句用于将Child指向左右儿子中较大值
        if (temp >= H->Element[Child])
            break;
        else
            H->Element[Parent] = H->Element[Child]; //移动temp到下一层
    }
    H->Element[Parent] = temp; //找到了适合temp的父节点位置，插入
    return MaxItem;
}
